package com.ronz.linkedlist;

import com.ronz.linkedlist.util.HeroNode;

import java.awt.*;

/**
 * @Description 单向环形链表解决约瑟夫问题
 * @Author Ronz
 * @Date 2020/12/25 10:14
 * @Version 1.0
 */
public class No7_Josepfu {

    public static void main(String[] args) {

        HeroNode node_1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node_2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node_3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node_4 = new HeroNode(4, "公孙胜", "入云龙");

        System.out.println("===============向环形链表中插入结点==================");
        HeroNode first = insertCircleList(null, node_1);
        first = insertCircleList(first, node_2);
        first = insertCircleList(first, node_3);
        first = insertCircleList(first, node_4);
        showList(first);

        System.out.println("===============约瑟夫游戏开始===============");
        josepfuGame(first,1,2);
    }

    /**
     * @Description 1. 插入结点到环形链表中
     * @Param []
     * @return void
     */
    public static HeroNode insertCircleList(HeroNode first, HeroNode node){
        // 判断链表是不是为空，如果为空，就直接插入
        if (first == null){
            first = node;
            // 因为要环形链表，而且只有一个结点，所以要我指向我自己
            first.next = node;
        }else{
            // 如果环形链表不为空
            HeroNode tempNode = first;
            while (true){
                // 如果到了环形链表的最后一个元素
                if (tempNode.next.getNo() == first.getNo()){
                    tempNode.next = node;
                    // 因为是环形链表，所以最后一个结点还要指向第一个结点
                    node.next = first;
                    break;
                }
                tempNode = tempNode.next;
            }
        }
        return first;
    }

    /**
     * @Description 2. 约瑟夫游戏开始
     * @Param [first, k, m] 从第 k 个人开始数，每次数 m 个
     * @return void
     */
    public static void josepfuGame(HeroNode first,int k, int m){
        if (first == null){
            System.out.println("链表为空！");
            return;
        }
        HeroNode helperNode = first;
        // 首先要到 第 k 个结点
        for (int i = 1; i < k; i++){
            helperNode = helperNode.next;
        }
        while (helperNode.next.getNo() != helperNode.getNo()){
            // 报数， m 个数也就是相当于向后移动 m-1 次，也就是要把第 m-1 个结点去掉
            // 由于单链表的特点，要去掉第 m-1 个结点，肯定是要让指针前一个结点，即第(m-2)个结点
            for (int j=0; j<m-2; j++){  // 让指针指向第 m-2 个结点
                helperNode = helperNode.next;
            }
            System.out.println(helperNode.next + "退出链表了!");
            helperNode.next = helperNode.next.next;

            // 因为下一轮要从刚刚去掉的结点的后面一个结点开始数数了，所以需要后移一位
            helperNode = helperNode.next;

//            i = (i + 1) % m;
//            // 每次 i == 0 的时候，就丢弃 helperNode.next 结点
//            if (i == 0){
//                System.out.println(helperNode.next + "退出链表了！");
//                helperNode.next = helperNode.next.next;
//                i = 1;
//            }
//            helperNode = helperNode.next;
        }
        System.out.println(helperNode + "退出链表了!");
    }
    /**
     * @Description 3. 打印单向环形链表
     * @Param []
     * @return void
     */
    public static void showList(HeroNode first){
        if (first == null){
            System.out.println("链表为空！");
            return;
        }
        HeroNode tempNode = first;
        while (true){
            if (tempNode.next.getNo() == first.getNo()){
                System.out.println(tempNode);
                break;
            }
            System.out.println(tempNode);
            tempNode = tempNode.next;
        }
    }
}
